"""P11 11.基础提升 哈希函数、哈希表、布隆过滤器、一致性哈希原理"""

from random import randint

"""
哈希函数：
1、输入域趋近无穷大
2、相同的输入拥有相同的输出
3、不同的输入输出相同（哈希碰撞）的几率极低
4、哈希函数输出的离散具有均匀性

哈希表：
根据数据通过哈希函数算出的值，放入表中相应位置的链中
N个数据的哈希表的扩容代价O(logN)
"""


class RandomPool:

    def __init__(self):
        self.map1 = dict()  # str -> index
        self.map2 = dict()  # index -> str
        self.size = 0

    def insert(self, key):
        """将key加入结构，不重复加入"""
        if key not in self.map1:
            self.map1[key] = self.size
            self.map2[self.size] = key
        self.size += 1

    def delete(self, key):
        """在结构中移除key"""
        if key not in self.map1:
            return
        last_str = self.map2[self.size - 1]
        key_index = self.map1[key]
        self.map1[last_str] = key_index
        self.map1.pop(key)
        self.map2[key_index] = last_str
        self.map2.pop(self.size - 1)
        self.size -= 1

    def getRandom(self):
        """等概率返回任意一个key"""
        return self.map2.get(randint(0, self.size))


"""
布隆过滤器：
总数据N，每个数据经过K个哈希函数输出的值分别%m，
得到的结果标记在长度为m的字节链上，这就是每个数据的特征。

在布隆过滤器中的数据一定可以拦截，不在布隆过滤器中的数据可能被错误拦截。

样本量：N               失误率：P
理论字节链长度：  m = - n * ln(P) / (ln(2))**2
理论哈希函数数量：K =  ln(2) * m / n
实际字节链长度：m'      实际哈希函数数量：k'
实际失误率：P = (1 - e**(- N * k' / m'))**k' 
"""


def get_bit_val(value: int, index: int) -> int:
    """获取value从右往左的第index字节位的值"""
    return (value >> index) & 1


def set_bit_1(value: int, index: int) -> int:
    """将value从右往左的第index字节位的值设为1"""
    return value | (1 << index)


def set_bit_0(value: int, index: int) -> int:
    """将value从右往左的第index字节位的值设为0"""
    return value & (~(1 << index))


"""
一致性哈希原理：

数据库的负载均衡是通过将数据的哈希值去模数据库数量来实现的，
相关词频的数据量要比较大才能适合负载均衡。

将数据库的哈希值放到一个哈希环链上，数据存放在最近的比它哈希值大的数据库。
方便数据库的增删，但是数据库在环上的位置不平衡

虚拟节点技术：
为各个数据库分配大量虚拟节点，虚拟节点的哈希值在环上标点。
根据数据库能力不同，可以分配不等量的虚拟节点来管理负载

"""